public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode nummy = new ListNode(0, head);
        ListNode node = nummy;
        while(node.next != null){
            node = reverse(node, k);
        }
        return nummy.next;
    }

    /**
     * return: 反转后的最后一个结点
     */
    ListNode reverse(ListNode parent, int k){
        /*
        ... <- prev  cur -> next -> ... 改为:
        ... <- prev <- cur  next -> ...
         */
        if(parent.next == null) return parent;
        ListNode prev = parent.next;
        ListNode cur = prev.next;
        if(cur == null) return prev;
        ListNode next = cur.next;
        for(int i = 1; i < k; i++){
            cur.next = prev;
            if(next == null){
                parent.next.next = null;
                parent.next = cur;
                if(i + 1 < k){
                    return reverse(parent, i + 1);
                }
                return cur;
            }
            prev = cur;
            cur = next;
            next = next.next;
        }
        ListNode ret = parent.next;
        parent.next.next = cur;
        parent.next = prev;

        return ret;
    }
}